1. Field of the Invention
The present invention relates generally to a cell placement apparatus and method for use in a layout design following a logic design in a computer aided design automation of LSIs or VLSIs and to a computer readable record medium having a cell placement program stored thereon. More particularly, it is directed to a cell placement apparatus and method for realizing an optimum cell placement with a restricted cell activity ratio of a high-density wiring region on a cell, as well as to a computer readable record medium on which a cell placement program is stored.
2. Description of the Related Arts
In a CAD system for automatically designing large-scale semiconductor integrated circuits such as VLSIs or LSIs with the aid of a computer, a logic design is first carried out for determining AND, OR or other cells and cell-to-cell connections (nets). Cell placement processing is then performed for determining locations of cells on a chip on the basis of a netlist acquired from the logic design. Wiring processing (routing) is finally effected for determining the wiring, that is, how to provide nets between the cells placed on the chip.
Known as the cell placement processing is for example a partitioning based placement algorithm. In the partitioning based placement algorithm, the entire chip is first partitioned into two regions so that all the cells are assigned to the two regions obtained as a result of the partitioning. A criterion for the cell assignment is a cost which is the number of nets connecting the two regions when the cells are assigned to the two regions. The grouping is so made as to minimize the cost. Such cell region partitioning and cell assignment are iterated until the partitioned blocks result in minimum blocks each corresponding to a single cell. In this case, if the cells become dense at one place as a result of the cell placement on the chip, it may be impossible to effect the wiring. Hence, the placement is carried out with a restriction condition of the cell distribution. In order to establish the restriction condition, cell activity ratios .rho.(1) and .rho.(2) of the two regions are first figured out from
.rho.(2)=s1/S1 PA1 .rho.(2)=s2/S2 PA1 where .alpha. is a positive constant. PA1 a rough wiring module for executing a rough wiring for the already placed cells; a high-density wiring region judging module which partitions the chip into blocks each having a predetermined size and detects a wiring density based on the rough wiring for each block, to judge whether a region is a high-density wiring region or not; and a restricted region deciding module which decides the high-density wiring region as a restricted region in which a cell activity ratio is restricted and allocates as a cell maximum activity ratio to the restricted region a lower activity ratio than an ordinary cell activity ratio. PA1 I) To let s1 and s2 be cell areas in a first region and a second region, respectively, which are obtained as a result of bisecting, s (=s1+s2) be a total cell area, S1 and S2 be areas of the first region and the second region, respectively, S1(i) be an area of a portion belonging to the first region within an i-th restricted region, S2(i) be an area of a portion belonging to the second region within the i-th restricted region, and .rho.(i) be a cell activity ratio specified for the i-th restricted region; PA1 II) To figure out areas S1(0) and S2(0) of portions having no cell activity ratio restriction in the first region and the second region, respectively, from EQU S1(0)=S1-.SIGMA.S1(i) EQU S2(0)=S2-.SIGMA.S2(i) PA1 III) To figure out an activity ratio .rho.(0) of a portion having no cell activity ratio restriction, from EQU .rho.(0)={(total cell area)-(total cell area of activity ratio specified regions)}/(total area)=[s-.SIGMA.{.rho.(i).times.(S1(i)+S2(i)}]/S1(0)+S2(0) PA1 IV) To figure out cell effective areas s1' and s2' in the first and second regions, respectively, based on the activity ratios .rho.(0) and .rho.(i), from EQU s1'=.rho.(0).times.S1(0)+.SIGMA.(.rho.(i).times.S1(i)) EQU s2'=.rho.(0).times.S2(0)+.SIGMA.(.rho.(i).times.S1(i)) PA1 V) To figure out converted areas S1' and S2' by proportionally dividing a total area of the first and second regions by ratios, to a total cell area s, of cell effective areas s1' and s2' in the first and second regions, respectively, using EQU S1'=(S1+S2).times.(s1'/s) EQU S2'=(S1+S2).times.(s2'/s) PA1 VI) To provide a control of grouping of cells effected by the partitioning based placing module so that an absolute value of a difference between ratios of cell areas s1 and s2 to the converted areas S1' and S2', respectively, of the first and second regions, respectively, satisfies a condition EQU .vertline.s1/S1'-s2/S2'.vertline..ltoreq..alpha. PA1 a restricted region specifying step for specifying a restricted region in which is restricted a cell activity ratio indicative of a ratio of a cell occupied area to the entire surface area of a chip and a cell maximum activity ratio of the restricted region; PA1 a restricted region managing step for accepting for management the restricted region and the cell maximum activity ratio specified in the restricted region specifying step; and PA1 a cell placing step for placing cells in such a manner that the cell activity ratio of the restricted region managed in the restricted region managing step does not exceed the cell maximum activity ratio. PA1 a restricted region specifying module for specifying both a restricted region in which is restricted a cell activity ratio indicative of a ratio of a cell occupied area to a chip surface area and a cell maximum activity ratio of the restricted region; PA1 a restricted region managing module for accepting for management the restricted region and the cell maximum activity ratio specified by the restricted region specifying module; and PA1 a cell placing module for placing cells in such a manner that the cell activity ratio of the restricted region managed by the restricted region managing module does not exceed the cell maximum activity ratio.
The cells are then grouped so as to meet a restriction condition given as a conditional expression that an absolute value of a difference between the activity ratios of the two regions should be equal to or less than a positive constant .alpha., that is, a restriction condition given as EQU .vertline.(s1/S1)-(s2/S2).vertline..ltoreq..alpha. (1)
An appropriate dispersion of the cells are thus achieved by placing the cells so as to fulfill the condition that the difference between the cell activity ratios upon the block partitioning lies within a certain range. Such a restriction condition for the cell activity ratios is called an area restriction.
In typical computer aided cell placement processing, however, all the cells are not newly placed on the chip. For example, clock signal sending cells, RAMs or other cells are already located previous to the automatic cell placement. For this reason, conventional cell placement processing having the area restriction defined as a cell placement restriction condition may suffer from an inconvenience that uneven wiring density may occur in the wiring processing which is carried out after the completion of the cell placement, if there exist already placed cells of which placement locations have been previously determined on the chip, due to nets connecting to the already placed cells. As a result of this, a portion having a higher wiring density must be given a lower cell activity ratio than the other portions upon the cell placement since it requires a larger area for the wiring than the areas required by the other portions. The wiring density could be substantially accurately estimated by an execution of rough wiring. A method is thus conceivable in which the rough wiring is performed at the time of completion of the cell placement with the addition of an operation for removing some cells from a high-density wiring portion. However, in the event of removing the cells from the high-density wiring portion for relocation to the other portions, the cell activity ratio restriction condition for the cell placement processing may collapse, which may result in an overall degradation of the cell placement quality and unfeasible wiring. Another algorithm such as simulated annealing would also be available to perform the operation for removing some cells from a high-density wiring portion for the relocation to the other portions while assuring the cell placement quality. However, this method may need more processing time although the cell placement quality is assured.
An approach to a reduction of the cell activity area in a specific region is a use of a cell placement inhibition region or a floor plan. However, the cell placement inhibition region is provided to entirely inhibit the placement of cells in a region. Therefore, in the event that the cell placement inhibition region is partially provided in a region to reduce the cell activity area, this may possibly induce a more serious inconvenience that the presence of this cell placement inhibition region may impose a size limitation of cells which can be placed therein, impeding the placement of larger cells. The floor plan is used to specify a region in which is arranged a module (macro cell) making up a certain logic. In case of the floor plan, the logic determines a unit to be controlled. This may make it hard to reduce the cell activity area of a high-density wiring region existing in a module by use of the floor plan. It may also be unfeasible for the floor plan to reduce the cell activity area of a high-density wiring region which exists between two modules. That is, both the cell placement inhibition region and the floor plan were conceived for the other objects, with no intention to reduce the cell activity area of a high-density wiring region. Thus, there have arisen deficiencies that existence of already placed cells or other cells on the chip may make the wiring difficult due to the occurrence of high-density portions of both the nets and cells and that the reexecution of the cell placement to avoid this may result in extended processing time.